package com.gorkr.hot100.medium;

import org.junit.Test;

/**
 * @author 张心宇 <zhangxinyu20@kuaishou.com>
 * Created on 2022-12-22
 */
public class M79WordSearch {

    private boolean res = false;

    public boolean exist(char[][] board, String word) {
        boolean[][] flag = new boolean[board.length][board[0].length];

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board,flag,word,i,j,0);
            }
        }
        return res;
    }

    private void dfs(char[][] board, boolean[][] flag, String word, int indexI, int indexJ, int step){
        if(board[indexI][indexJ] != word.charAt(step)){
            return;
        }
        if(step==word.length()-1){
            this.res = true;
            return;
        }
        if(step>word.length()-1){
            return;
        }
        // 左
        flag[indexI][indexJ]=true;
        if( indexJ-1>=0 && !flag[indexI][indexJ-1] ){
            dfs(board,flag, word,indexI,indexJ-1,step+1);
        }
        // 右
        if(indexJ+1<board[0].length && !flag[indexI][indexJ+1] ){
        }
        // 上
        if( indexI-1>=0 && !flag[indexI-1][indexJ]){
            dfs(board,flag,word,indexI-1,indexJ,step+1);
        }
        // 下
        if( indexI+1<board.length && !flag[indexI+1][indexJ]){
            dfs(board,flag,word,indexI+1,indexJ,step+1);
        }
        flag[indexI][indexJ]=false;
    }

    @Test
    public void test(){
        char[][] board = {{'C','A','A'},{'A','A','A'},{'B','C','D'}};
        System.out.println(exist(board, "AAB"));
    }
}
